﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace Misc
{
    class Program
    {
        static void Main(string[] args)
        {
            //Helper.FindFirstOne();
            //SortAnagramWise();
            //BSTAddRemove();

            //StringToFloat();
            //Console.WriteLine(NthPower(8, 2));
            Console.WriteLine(power(3, 4));
            Console.ReadKey();
        }

        private static int NthPower(int n, int p)
        {
            if (n == 0 || n == 1) return n;
            return n << (p - 1);
        }

        public static double power(long x, int n)
        {

            double pow = 1L;
            if (n == 0)
                return 1;
            if (n == 1)
                return x;
            pow = power(x, n / 2);
            return (n % 2 == 0) ? pow * pow : pow * pow * x;
        }

        private static void StringToFloat()
        {
            char[] s = "0.1237658".ToCharArray();
            int i = 0;
            double sum = 0;
            for (i = 0; i < s.Length && s[i].ToString() != "."; i++)
            {
                sum = (sum + Convert.ToInt32(s[i]) - 48) * 10;                           
            }
            sum /= 10;
            for (int j = i + 1; j < s.Length; j++)
            {
                sum += Convert.ToInt32(s[j] - 48) / Math.Pow(10, j - i);
            }
            Console.WriteLine(sum);
        }

        private static void BSTAddRemove()
        {
            BST tree = new BST();
            tree.Add(5);
            tree.Add(7);
            tree.Add(3);
            tree.Add(8);
            tree.Add(1);
            tree.Add(2);
            BST.PrintTree(tree.rootNode);
            tree.Remove(3);
            BST.PrintTree(tree.rootNode);
        }

        private static void SortAnagramWise()
        {
            string[] a = { "abc", "god", "cab", "man", "dog", "bac" };
            int i = 0, j = 1;

            while (i < a.Length)
            {
                while (j < a.Length)
                {
                    if (IsAnagram(a[i], a[j]))
                    {
                        string temp = a[j];
                        int k = j;
                        i++;
                        while (k != i)
                        {
                            a[k] = a[k - 1];
                            k--;
                        }
                        a[i] = temp;
                    }
                    j++;
                }
                i++;
                j = i + 1;
            }
            foreach (var item in a)
            {
                Console.WriteLine(item);
            }
        }

        private static bool IsAnagram(string p, string q)
        {
            bool flag = true;
            if (p.Length != q.Length)
                return false;
            foreach (char ch in p)
                if (!q.Contains(ch))
                {
                    flag = false;
                    break;
                }
            return flag;
        }
        //static void Main(string[] args)
        //{
        //    int[] input = { 10, 8, 2, 20, 31, 14, 7 };
        //    //char[] str = Helper.removeDuplicates("bbacbbaaa".ToCharArray());
        //    //char[] str = RemoveDuplicatesChar("bbacbbaaad".ToCharArray());
        //    //char[] output = RemoveDuplicatesCharHash("bbacbbaaadaaz".ToCharArray());
        //    //int[] output = RemoveDuplicatesInt(input);
        //    //foreach(int i in output)
        //    //Console.Write(i);
        //    //Console.WriteLine(GetMaxSum(input));
        //    //Console.WriteLine(AddTwoNumbers(165, 394));
        //    //Console.WriteLine(SubtractTwoNumbers(5, 2));
        //    //Console.WriteLine(IncrementByOne(5));
        //    //Console.WriteLine(SubtractByOne(7));
        //    //Console.WriteLine("index : " + BinarySearch(input, 0));
        //    foreach(int i in MergeSort(input))
        //    Console.WriteLine(i);
        //    Console.ReadKey();
        //}

        #region Commented
        private static string SubtractTwoNumbers(int a, int b)
        {
            return null;
        }

        private static int IncrementByOne(int a)
        {
            int i = 1;
            while(true)
            {
                a = a ^ i;
                if((a & i) != 0)
                    break;
                i = i << 1;
            }            
            return a;
        }

        private static int SubtractByOne(int a)
        {
            int i = 1;
            while (true)
            {
                a = a ^ i;
                if ((a & i) != 0)
                    break;
                i = i << 1;
            }
            return a;
        }

        static char[] RemoveDuplicatesChar(char[] str)
        {
            int tail = 1;
            for (int i = 1; i < str.Length; i++ )
            {
                int j;
                for (j = 0; j < tail; j++)
                {
                    if (str[i] == str[j])
                        break;
                }
                if (j == tail)
                {
                    str[tail] = str[i];
                    tail++;                    
                }
            }
            for (int i = tail; i < str.Length; i++)
                str[i] = '\0';
            return str;
        }

        static int[] RemoveDuplicatesInt(int[] str)
        {
            int tail = 1;
            for (int i = 1; i < str.Length; i++)
            {
                int j;
                for (j = 0; j < tail; j++)
                {
                    if (str[i] == str[j])
                        break;
                }
                if (j == tail)
                {
                    str[tail] = str[i];
                    tail++;
                }
            }
            for (int i = tail; i < str.Length; i++)
                str[i] = 0;
            return str;
        }

        static char[] RemoveDuplicatesCharHash(char[] str)
        {
            char[] hashTable = new char[256];
            char[] output = new char[str.Length];
            int count = 0;
            for (int i = 1; i < str.Length; i++)
            {
                if (hashTable[(int)str[i]] == 0)
                {
                    hashTable[(int)str[i]] = str[i];
                    output[count++] = str[i];
                }
            }
            return output;
        }

        static int GetMaxSum(int[] input)
        {
            int maxsum = input[0];
            int sum = 0;
            foreach (int i in input)
            {
                sum += i;
                if (sum > maxsum)
                    maxsum = sum;
                else if (sum < 0)
                    sum = 0;
            }
            return maxsum;
        }

        static int AddTwoNumbers(int a, int b)
        {
            if (b == 0)
                return a;
            int s = a ^ b;
            int c = (a & b) << 1 ;
            return AddTwoNumbers(s, c);
        }

        static int BinarySearch(int[] a, int n)
        {
            return BSearch(a, 0, a.Length - 1, n);
        }

        private static int BSearch(int[] a, int low, int max, int n)
        {
            int mid = (low + max) / 2;
            if (a[mid] == n)
                return mid;
            else if (n > a[mid] && n <= a[max])
                return BSearch(a, mid + 1, max, n);
            else if (n < a[mid] && n >= a[low])
                return BSearch(a, low, mid - 1, n);
            else 
                return -1;
        }

        private static int[] BubbleSort(int[] a)
        {
            for (int i = 0; i < a.Length; i++)
            {
                for (int j = 0; j < a.Length - i - 1; j++)
                {
                    if (a[j] > a[j + 1])
                    {
                        a[j] = a[j] ^ a[j + 1];
                        a[j + 1] = a[j] ^ a[j + 1];
                        a[j] = a[j] ^ a[j + 1];
                    }
                }
            }
            return a;
        }

        private static int[] SelectionSort(int[] a)
        {
            for (int i = 0; i < a.Length; i++)
            {
                for (int j = i + 1; j < a.Length; j++)
                {
                    if (a[i] > a[j])
                    {
                        a[i] = a[i] ^ a[j];
                        a[j] = a[i] ^ a[j];
                        a[i] = a[i] ^ a[j];
                    }
                }
            }
            return a;
        }

        private static int[] InsertionSort(int[] a)
        {
            for (int i = 0; i < a.Length; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (a[i] < a[j])
                    {
                        int temp = a[i];
                        int k = i;
                        while (k > j)
                        {
                            a[k] = a[k - 1];
                            k--;
                        }
                        a[j] = temp;
                    }
                }
            }
            return a;
        }

        private static int[] QuickSort(int[] a)
        {
            return QSort(a, 0, a.Length - 1);
        }

        private static int[] QSort(int[] a, int low, int pivot)
        {
            if (low >= pivot)
                return a;

            int i = low;
            int j = pivot;


            while (true)
            {
                while (a[i] <= a[pivot])
                {
                    if (i >= j) break;
                    i++;
                }
                while (a[j] >= a[pivot])
                {
                    if (j <= i) break;
                    j--;
                }
                if (i != j)
                    Swap(a, i, j);
                if (i >= j)
                {
                    Swap(a, i, pivot);
                    break;
                }
            }
            QSort(a, low, i - 1);
            QSort(a, i + 1, pivot);
            return a;
        }

        private static void Swap(int[] a, int p, int q)
        {
            int temp = a[p];
            a[p] = a[q];
            a[q] = temp;
        }

        private static int[] MergeSort(int[] a)
        {
            return MSort(a, 0, a.Length - 1);
        }

        private static int[] MSort(int[] a, int start, int end)
        {
            if (start == end)
                return a;
            int mid = (start + end)/2;
            MSort(a, start, mid);
            MSort(a, mid + 1, end);

            List<int> m = new List<int>();
            List<int> n = new List<int>();
            for(int i = start; i <= mid; i++)
                m.Add(a[i]);
            for(int j = mid + 1; j <= end; j++)
                n.Add(a[j]);

            int p = 0;
            int q = 0;
            while (p < m.Count && q < n.Count)
            {
                if (m[p] < n[q])
                {
                    a[start + p + q] = m[p];
                    p++;
                }
                else
                {
                    a[start + p + q] = n[q];
                    q++;
                }
            }

            if (q == n.Count)
            {
                for (int k = p; k < m.Count; k++)
                    a[start + q + k] = m[k];
            }
            if (p == m.Count)
            {
                for (int k = q; k < n.Count; k++)
                    a[start + p + k] = n[k];
            }            
            //while (p < m.Count)
            //{
            //    a[start + p + q] = m[p];
            //    p++;
            //}
            //while (q < n.Count)
            //{
            //    a[start + p + q] = n[q];
            //    q++;
            //}
            return a;
        }
        #endregion
    }
}
